package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

/**
 * 572. 另一棵树的子树
 * @Author: cookLee
 * @Date: 2024-08-04
 */
public class IsSubtree {

    /**
     * 主
     * \
     * 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
     * 输出：true
     * \
     * 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
     * 输出：false
     * \
     * @param args args
     */
    public static void main(String[] args) {
        IsSubtree isSubtree = new IsSubtree();
        TreeNode root = new TreeNode(3,new TreeNode(4,new TreeNode(1),new TreeNode(2)),new TreeNode(5));
        TreeNode subRoot = new TreeNode(4,new TreeNode(1),new TreeNode(2));
        System.out.println(isSubtree.isSubtree(root, subRoot));
    }

    /**
     * 是子树
     *
     * @param root    根
     * @param subRoot 子根
     * @return boolean
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return this.helper(root, subRoot);
    }

    /**
     * 深度搜索助手类
     *
     * @param root    根
     * @param subRoot 子根
     * @return boolean
     */
    private boolean helper(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return this.check(root, subRoot) || this.check(root.left, subRoot) || this.check(root.right, subRoot);
    }

    /**
     * 检查
     * 检查是否有符合条件的数据
     *
     * @param subRoot 子根
     * @param child   儿童
     * @return boolean
     */
    private boolean check(TreeNode child, TreeNode subRoot) {
        if (child == null && subRoot == null) {
            return true;
        }
        if (child == null || subRoot == null || child.val != subRoot.val) {
            return false;
        }
        return this.check(child.left, subRoot.left) && this.check(child.right, subRoot.right);
    }

}
